package com.gitee.ywj1352.kaishi.Test;


import org.junit.Test;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextDouble()) {// 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
            double v = in.nextDouble();
        }
    }

    @Test
    public void fun1() {
        int[] arr = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxArea2(arr));
    }


    public int maxArea(int[] height) {
        int c = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                c = Math.max(Math.min(height[i], height[j]) * (j - i), c);
            }
        }
        return c;
    }

    public int maxArea2(int[] height) {
        int c = 0;
        int i = 0;
        int j = height.length - 1;

        while (i < j) {
            c = Math.max(c, (j - i) * Math.min(height[i], height[j]));
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return c;
    }

    @Test
    public void fun3() {
//        System.out.println(findPaths(7, 6, 13, 0, 2));
        System.out.println(findPaths3(0, 2, 3, 0, 0));
    }

    private HashMap<String, Integer> map = new HashMap<>();

    public int findPaths(int m, int n, int N, int i, int j) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        queue.add(j);
        queue.add(N);
        int c = 0;
        while (!queue.isEmpty()) {
            Integer ri = queue.remove();
            Integer rj = queue.remove();
            Integer rN = queue.remove();
            String key = ri + ":" + rj + ":" + rN;
            if (map.get(key) != null && rN > 0) {
                c += map.get(key);
                continue;
            }
            int rC = 0;
            //向上
            if (ri - 1 > -1 && rN - 1 >= 0) {
                if (rN != 0) {
                    queue.add(ri - 1);
                    queue.add(rj);
                    queue.add(rN - 1);
                }
            } else {
                if (rN - 1 >= 0) {
                    rC++;
                }
            }
            //向左
            if (rj - 1 >= 0 && rN - 1 >= 0) {
                if (rN != 0) {
                    queue.add(ri);
                    queue.add(rj - 1);
                    queue.add(rN - 1);
                }
            } else {
                if (rN - 1 >= 0) {
                    rC++;
                }
            }
            //向下
            if (ri + 1 < m && rN - 1 >= 0) {
                if (rN != 0) {
                    queue.add(ri + 1);
                    queue.add(rj);
                    queue.add(rN - 1);
                }
            } else {
                if (rN - 1 >= 0) {
                    rC++;
                }
            }
            //向右
            if (rj + 1 < n && rN - 1 >= 0) {
                if (rN != 0) {
                    queue.add(ri);
                    queue.add(rj + 1);
                    queue.add(rN - 1);
                }
            } else {
                if (rN - 1 >= 0) {
                    rC++;
                }
            }
            map.put(key, rC);
            c += rC;
        }
        return c;
    }

    public int findPaths2(int m, int n, int N, int i, int j) {
        if (N == 0) return 0;
        int mod = 1000000007;
        //走路的步数
        int[][] direct = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int[][] dp = new int[m][n];
        for (int k = 0; k < N; k++) {
            int[][] tmp = new int[m][n];
            for (int x = 0; x < m; x++) {
                for (int y = 0; y < n; y++) {
                    for (int[] d : direct) {
                        if (x + d[0] < 0 || x + d[0] >= m || y + d[1] < 0 || y + d[1] >= n) {
                            tmp[x][y]++;
                        } else {
                            tmp[x][y] = (tmp[x][y] + dp[x + d[0]][y + d[1]]) % mod;
                        }
                    }
                }
            }
            dp = tmp;
        }
        return dp[i][j];
    }

    public int findPaths3(int m, int n, int N, int i, int j) {
        int[][][] dp = new int[m][n][N + 1];
        int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < m; y++) {
                for (int z = 0; z < n; z++) {
                    for (int[] dir : dirs) {
                        int nz = z + dir[0];
                        int ny = y + dir[1];
                        if (nz < 0 || nz > m || ny < 0 || ny > n) {
                            dp[y][z][x] += 1;
                        } else {
                            dp[y][z][x] = dp[y][z][x] + dp[ny][nz][x];
                        }
                    }
                }
            }
        }
        return 1;
    }

    //Definition for a binary tree node.
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private TreeMap<Integer, List<Integer>> levelOrderMap = new TreeMap<>();

    //DFS 做题
    public void zigzagLevelOrder(TreeNode root, int depth) {
        if (root == null) return;
        TreeNode lNode = root.left;
        TreeNode rNode = root.right;
        zigzagLevelOrder(lNode, depth + 1);
        zigzagLevelOrder(rNode, depth + 1);
        if (levelOrderMap.get(depth) == null) {
            levelOrderMap.put(depth, new ArrayList<>());
        }
        List<Integer> integers = levelOrderMap.get(depth);
        integers.add(root.val);
    }

    /**
     *  3
     * / \
     * 9  20
     *   /  \
     *  15   7
     */
    @Test
    public void fun10() {
        TreeNode tree3 = new TreeNode(3);
        TreeNode tree9 = new TreeNode(9);
        TreeNode tree20 = new TreeNode(20);
        TreeNode tree15 = new TreeNode(15);
        TreeNode tree7 = new TreeNode(7);
        tree3.left = tree9;
        tree3.right = tree20;
        tree20.left = tree15;
        tree20.right = tree7;
        zigzagLevelOrder(tree3, 0);
        List<List<Integer>>list = new ArrayList<>();
        for (Map.Entry<Integer, List<Integer>> entry : levelOrderMap.entrySet()) {
            Integer k = entry.getKey();
            List<Integer> v = entry.getValue();
            if (k % 2 != 0) {
                Collections.reverse(v);
            }
            list.add(v);
        }

        System.out.println(list);
    }


}